{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Cost to Buy Apples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph #array #shortest-path #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图 #数组 #最短路 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minCost"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #购买苹果的最低成本"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数&nbsp; <code>n</code>，表示从 <code>1</code> 到 <code>n</code> 的 <code>n</code> 个城市。还给你一个&nbsp;<strong>二维&nbsp;</strong>数组 <code>roads</code>，其中 <code>roads[i] = [a<sub>i</sub>, b<sub>i</sub>, cost<sub>i</sub>]</code> 表示在城市 <code>a<sub>i</sub></code> 和 <code>b<sub>i</sub></code> 之间有一条双向道路，其旅行成本等于 <code>cost<sub>i</sub></code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>你可以在&nbsp;<strong>任何&nbsp;</strong>城市买到苹果，但是有些城市买苹果的费用不同。给定数组 <code>appleCost</code> ，其中 <code>appleCost[i]</code>&nbsp;是从城市 <code>i</code> 购买一个苹果的成本。</p>\n",
    "\n",
    "<p>你从某个城市开始，穿越各种道路，最终从&nbsp;<strong>任何一个&nbsp;</strong>城市买&nbsp;<strong>一个&nbsp;</strong>苹果。在你买了那个苹果之后，你必须回到你&nbsp;<strong>开始的&nbsp;</strong>城市，但现在所有道路的成本将&nbsp;<strong>乘以&nbsp;</strong>一个给定的因子 <code>k</code>。</p>\n",
    "\n",
    "<p>给定整数 <code>k</code>，返回<em>一个大小为 <code>n</code> 的数组 <code>answer</code>，其中 <code>answer[i]</code>&nbsp;是从城市 <code>i</code> 开始购买一个苹果的&nbsp;<strong>最小&nbsp;</strong>总成本。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/11/15/graph55.png\" style=\"width: 241px; height: 309px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 4, roads = [[1,2,4],[2,3,2],[2,4,5],[3,4,1],[1,3,4]], appleCost = [56,42,102,301], k = 2\n",
    "<strong>输出:</strong> [54,42,48,51]\n",
    "<strong>解释:</strong> 每个起始城市的最低费用如下:\n",
    "- 从城市 1 开始:你走路径 1 -&gt; 2，在城市 2 买一个苹果，最后走路径 2 -&gt; 1。总成本是 4 + 42 + 4 * 2 = 54。\n",
    "- 从城市 2 开始:你直接在城市 2 买一个苹果。总费用是 42。\n",
    "- 从城市 3 开始:你走路径 3 -&gt; 2，在城市 2 买一个苹果，最后走路径 2 -&gt; 3。总成本是 2 + 42 + 2 * 2 = 48。\n",
    "- 从城市 4 开始:你走路径 4 -&gt; 3 -&gt; 2，然后你在城市 2 购买，最后走路径 2 -&gt; 3 -&gt; 4。总成本是 1 + 2 + 42 + 1 * 2 + 2 * 2 = 51。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/11/15/graph4.png\" style=\"width: 167px; height: 309px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 3, roads = [[1,2,5],[2,3,1],[3,1,2]], appleCost = [2,3,1], k = 3\n",
    "<strong>输出:</strong> [2,3,1]\n",
    "<strong>解释:</strong> 在起始城市买苹果总是最优的。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= roads.length &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "\t<li><code>1 &lt;= cost<sub>i</sub> &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>appleCost.length == n</code></li>\n",
    "\t<li><code>1 &lt;= appleCost[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 100</code></li>\n",
    "\t<li>\n",
    "\t<p data-group=\"1-1\">没有重复的边。</p>\n",
    "\t</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-cost-to-buy-apples](https://leetcode.cn/problems/minimum-cost-to-buy-apples/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-cost-to-buy-apples](https://leetcode.cn/problems/minimum-cost-to-buy-apples/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[[1,2,4],[2,3,2],[2,4,5],[3,4,1],[1,3,4]]\\n[56,42,102,301]\\n2', '3\\n[[1,2,5],[2,3,1],[3,1,2]]\\n[2,3,1]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        x, y = startPos\n",
    "        X, Y = homePos\n",
    "        ans = sum(rowCosts[x+1:X+1]) if x < X else sum(rowCosts[X:x])\n",
    "        ans += sum(colCosts[y+1:Y+1]) if y < Y else sum(colCosts[Y:y])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        m = len(rowCosts)\n",
    "        n = len(colCosts)\n",
    "        sx,sy = startPos\n",
    "        tx,ty = homePos\n",
    "        if sx==tx and sy==ty:\n",
    "            return 0\n",
    "        smallx = sx if sx<tx else tx\n",
    "        largex = tx if sx<tx else sx\n",
    "        smally = sy if sy<ty else ty\n",
    "        largey = ty if sy<ty else sy\n",
    "        res = 0\n",
    "        if largex!=smallx:\n",
    "            for i in range(smallx+1, largex):\n",
    "                res += rowCosts[i]\n",
    "            res += rowCosts[tx]\n",
    "        if largey!=smally:\n",
    "            for i in range(smally+1, largey):\n",
    "                res += colCosts[i]\n",
    "            res += colCosts[ty]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minCost(self, startPos, homePos, rowCosts, colCosts):\n",
    "        return (sum(rowCosts[startPos[0] + 1 : homePos[0] + 1]) if startPos[0] < homePos[0] else sum(rowCosts[homePos[0] : startPos[0]]) if startPos[0] > homePos[0] else 0) \\\n",
    "             + (sum(colCosts[startPos[1] + 1 : homePos[1] + 1]) if startPos[1] < homePos[1] else sum(colCosts[homePos[1] : startPos[1]]) if startPos[1] > homePos[1] else 0)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "\n",
    "        \n",
    "        \n",
    "        minx, maxx = min(startPos[0], homePos[0]), max(startPos[0], homePos[0])\n",
    "        miny, maxy = min(startPos[1], homePos[1]), max(startPos[1], homePos[1])\n",
    "        ret = sum(rowCosts[i] for i in range(minx, maxx + 1)) + sum(colCosts[i] for i in range(miny, maxy + 1))\n",
    "        return ret - rowCosts[startPos[0]] - colCosts[startPos[1]]\n",
    "        \n",
    "        \n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        result = 0\n",
    "        if(startPos[0] > homePos[0]):\n",
    "            result += sum(rowCosts[homePos[0]:startPos[0]])\n",
    "        else:\n",
    "            result += sum(rowCosts[startPos[0]+1:homePos[0]+1])\n",
    "        if(startPos[1] > homePos[1]):\n",
    "            result += sum(colCosts[homePos[1]:startPos[1]])\n",
    "        else:\n",
    "            result += sum(colCosts[startPos[1]+1:homePos[1]+1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        result = 0\n",
    "        for i in self.getSteps(startPos[0], homePos[0]):\n",
    "            result += rowCosts[i]\n",
    "        for i in self.getSteps(startPos[1], homePos[1]):\n",
    "            result += colCosts[i]\n",
    "        return result\n",
    "\n",
    "    def getSteps(self, startPos: int, endPos: int):\n",
    "        step = 1 if startPos <= endPos else -1\n",
    "        return range(startPos + step, endPos + step, step)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        result = 0\n",
    "        if(startPos[0] > homePos[0]):\n",
    "            result += sum(rowCosts[homePos[0]:startPos[0]])\n",
    "        else:\n",
    "            result += sum(rowCosts[startPos[0]+1:homePos[0]+1])\n",
    "        if(startPos[1] > homePos[1]):\n",
    "            result += sum(colCosts[homePos[1]:startPos[1]])\n",
    "        else:\n",
    "            result += sum(colCosts[startPos[1]+1:homePos[1]+1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        res = 0\n",
    "        if startPos[0] < homePos[0]:res += sum(rowCosts[startPos[0] + 1:homePos[0] + 1])\n",
    "        else: res += sum(rowCosts[homePos[0]:startPos[0]])\n",
    "        if startPos[1] < homePos[1]:res += sum(colCosts[startPos[1] + 1:homePos[1] + 1])\n",
    "        else: res += sum(colCosts[homePos[1]:startPos[1]])\n",
    "        \n",
    "        return  res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        x0, y0 = startPos\n",
    "        x1, y1= homePos\n",
    "        ans = -rowCosts[x0] - colCosts[y0]\n",
    "        if x0 > x1:\n",
    "            x0, x1 = x1, x0\n",
    "        if y0 > y1:\n",
    "            y0, y1 = y1, y0\n",
    "        for cost in rowCosts[x0:x1+1]:\n",
    "            ans += cost\n",
    "        for cost in colCosts[y0:y1+1]:\n",
    "            ans += cost\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        r1, c1 = startPos[0], startPos[1]\n",
    "        r2, c2 = homePos[0], homePos[1]\n",
    "        res = 0   # 总代价\n",
    "        # 移动至家所在行，判断行间移动方向并计算对应代价\n",
    "        if r2 >= r1:\n",
    "            for i in range(r1 + 1, r2 + 1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(r2, r1):\n",
    "                res += rowCosts[i]\n",
    "        # 移动至家所在位置，判断列间移动方向并计算对应代价\n",
    "        if c2 >= c1:\n",
    "            for i in range(c1 + 1, c2 + 1):\n",
    "                res += colCosts[i]\n",
    "        else:\n",
    "            for i in range(c2, c1):\n",
    "                res += colCosts[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        result = 0\n",
    "        if(startPos[0] > homePos[0]):\n",
    "            result += sum(rowCosts[homePos[0]:startPos[0]])\n",
    "        else:\n",
    "            result += sum(rowCosts[startPos[0]+1:homePos[0]+1])\n",
    "        if(startPos[1] > homePos[1]):\n",
    "            result += sum(colCosts[homePos[1]:startPos[1]])\n",
    "        else:\n",
    "            result += sum(colCosts[startPos[1]+1:homePos[1]+1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        return sum(rowCosts[x] for x in range(min(startPos[0], homePos[0]), max(startPos[0], homePos[0]) + 1)) \\\n",
    "         + sum(colCosts[x] for x in range(min(startPos[1], homePos[1]), max(startPos[1], homePos[1]) + 1)) \\\n",
    "         - rowCosts[startPos[0]] - colCosts[startPos[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        x0, y0, x1, y1 = startPos[0], startPos[1], homePos[0], homePos[1]\n",
    "        ans = -rowCosts[x0] - colCosts[y0] # 初始的行列无需计算\n",
    "        if x0 > x1: \n",
    "            x0, x1 = x1, x0 # 交换位置，保证 x0 <= x1\n",
    "        if y0 > y1: \n",
    "            y0, y1 = y1, y0 # 交换位置，保证 y0 <= y1\n",
    "        for cost in rowCosts[x0 : x1+1]:\n",
    "            ans += cost # 统计答案\n",
    "        for cost in colCosts[y0 : y1+1]:\n",
    "            ans += cost # 统计答案\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        ans = 0\n",
    "        if startPos[0] != homePos[0]:\n",
    "            if startPos[0] < homePos[0]:\n",
    "                ans += sum(rowCosts[startPos[0]+1:homePos[0]+1])\n",
    "            else:\n",
    "                ans += sum(rowCosts[homePos[0]:startPos[0]])\n",
    "        if startPos[1] != homePos[1]:\n",
    "            if startPos[1] < homePos[1]:\n",
    "                ans += sum(colCosts[startPos[1]+1:homePos[1]+1])\n",
    "            else:\n",
    "                ans += sum(colCosts[homePos[1]:startPos[1]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        si, sj = startPos\n",
    "        ei, ej = homePos\n",
    "        \n",
    "        si, ei = (si, ei) if si <= ei else (ei, si)\n",
    "        sj, ej = (sj, ej) if sj <= ej else (ej, sj)\n",
    "\n",
    "        return (\n",
    "            sum(rowCosts[si:ei + 1])\n",
    "            + sum(colCosts[sj:ej + 1])\n",
    "            - rowCosts[startPos[0]]\n",
    "            - colCosts[startPos[1]]\n",
    "        )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        # 代价都是正的，所以不可绕路\n",
    "        # 贪心找x, y 较小分量即可\n",
    "        x1, y1, x2, y2 = startPos[0], startPos[1], homePos[0], homePos[1]\n",
    "\n",
    "        ans = -rowCosts[x1] - colCosts[y1]\n",
    "        # 水平移动代价\n",
    "        if x1 > x2:\n",
    "            x1, x2 = x2, x1\n",
    "        for i in range(x1, x2+1):\n",
    "            ans += rowCosts[i]\n",
    "        \n",
    "        # 垂直移动代价\n",
    "        if y1 > y2:\n",
    "            y1, y2 = y2, y1\n",
    "        for i in range(y1, y2+1):\n",
    "            ans += colCosts[i]\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "\n",
    "        if homePos == startPos:\n",
    "            return 0\n",
    "\n",
    "        st = startPos[0]\n",
    "        flag = 1\n",
    "        if startPos[0] > homePos[0]:\n",
    "            flag = -1 \n",
    "        cst = 0\n",
    "        while st != homePos[0]:\n",
    "            st += flag\n",
    "            cst += rowCosts[st]\n",
    "\n",
    "        st = startPos[1]\n",
    "        flag = 1\n",
    "        if startPos[1] > homePos[1]:\n",
    "            flag = -1 \n",
    "\n",
    "        while st != homePos[1]:\n",
    "            st += flag\n",
    "            cst += colCosts[st]\n",
    "\n",
    "        return cst        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        rmin = min(startPos[0], homePos[0])\n",
    "        rmax = max(startPos[0], homePos[0])\n",
    "        cmin = min(startPos[1], homePos[1])\n",
    "        cmax = max(startPos[1], homePos[1])\n",
    "\n",
    "        ans = sum(rowCosts[rmin:rmax+1]) + sum(colCosts[cmin:cmax+1])\n",
    "        ans -= rowCosts[startPos[0]]\n",
    "        ans -= colCosts[startPos[1]]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        x,y=startPos[0],startPos[1]\n",
    "        a,b=homePos[0],homePos[1]\n",
    "        ans=0\n",
    "        if x<a:\n",
    "            ans+=sum(rowCosts[x+1:a+1])\n",
    "        else:\n",
    "            ans+=sum(rowCosts[a:x])\n",
    "        if y<b:\n",
    "            ans+=sum(colCosts[y+1:b+1])\n",
    "        else:\n",
    "            ans+=sum(colCosts[b:y])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        r1, c1 = startPos[0], startPos[1]\n",
    "        r2, c2 = homePos[0], homePos[1]\n",
    "        res = 0   # 总代价\n",
    "        # 移动至家所在行，判断行间移动方向并计算对应代价\n",
    "        if r2 >= r1:\n",
    "            for i in range(r1 + 1, r2 + 1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(r2, r1):\n",
    "                res += rowCosts[i]\n",
    "        # 移动至家所在位置，判断列间移动方向并计算对应代价\n",
    "        if c2 >= c1:\n",
    "            for i in range(c1 + 1, c2 + 1):\n",
    "                res += colCosts[i]\n",
    "        else:\n",
    "            for i in range(c2, c1):\n",
    "                res += colCosts[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        startRow, endRow = startPos[0], homePos[0]\n",
    "        startCol, endCol = startPos[1], homePos[1]\n",
    "        ans = 0\n",
    "        if startRow < endRow:\n",
    "            for i in range(startRow + 1, endRow + 1):\n",
    "                ans += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(startRow - 1, endRow - 1, -1):\n",
    "                ans += rowCosts[i]\n",
    "        if startCol < endCol:\n",
    "            for i in range(startCol + 1, endCol + 1):\n",
    "                ans += colCosts[i]\n",
    "        else:\n",
    "            for i in range(startCol - 1, endCol - 1, -1):\n",
    "                ans += colCosts[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        result = 0\n",
    "        for i in self.getSteps(startPos[0], homePos[0]):\n",
    "            result += rowCosts[i]\n",
    "        for i in self.getSteps(startPos[1], homePos[1]):\n",
    "            result += colCosts[i]\n",
    "        return result\n",
    "\n",
    "    def getSteps(self, startPos: int, endPos: int):\n",
    "        step = 1 if startPos <= endPos else -1\n",
    "        return range(startPos + step, endPos + step, step)\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    print(list(Solution().getSteps(5,2)))\n",
    "    print(Solution().minCost([5,5] ,[5,2] ,[7,1,3,3,5,3,22,10,23],[5,5,6,2,0,16]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        ans=0\n",
    "        step= -1 if startPos[0]>homePos[0] else 1\n",
    "        for i in range(startPos[0]+step, homePos[0]+step, step):\n",
    "            ans+=rowCosts[i]\n",
    "        step= -1 if startPos[1]>homePos[1] else 1\n",
    "        for i in range(startPos[1], homePos[1], step):\n",
    "            ans+=colCosts[i+step]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        sx, sy = startPos\n",
    "        hx, hy = homePos\n",
    "        \n",
    "        ans = 0\n",
    "        if sx <= hx:\n",
    "            ans += sum(rowCosts[i] for i in range(sx+1, hx+1))\n",
    "        else:\n",
    "            ans += sum(rowCosts[i] for i in range(hx, sx))\n",
    "        \n",
    "        if sy <= hy:\n",
    "            ans += sum(colCosts[i] for i in range(sy+1, hy+1))\n",
    "        else:\n",
    "            ans += sum(colCosts[i] for i in range(hy, sy))\n",
    "        \n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        ans=0\n",
    "        step= -1 if startPos[0]>homePos[0] else 1\n",
    "        for i in range(startPos[0], homePos[0], step):\n",
    "            ans+=rowCosts[i+step]\n",
    "        step= -1 if startPos[1]>homePos[1] else 1\n",
    "        for i in range(startPos[1], homePos[1], step):\n",
    "            ans+=colCosts[i+step]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        if startPos == homePos:\n",
    "            return 0\n",
    "\n",
    "\n",
    "        def hp(h, s, costs):\n",
    "            dx = h - s \n",
    "\n",
    "            ans = 0\n",
    "\n",
    "            if dx == 0:\n",
    "                pass\n",
    "            elif dx > 0:\n",
    "                for k in range(s + 1, h + 1):\n",
    "                    ans += costs[k]\n",
    "            else:\n",
    "                for k in range(h, s):\n",
    "                    ans += costs[k]\n",
    "            \n",
    "            return ans\n",
    "\n",
    "        return hp(homePos[0], startPos[0], rowCosts) + hp(homePos[1], startPos[1], colCosts)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        dx, dy = 0, 0\n",
    "        if startPos[0] <= homePos[0]:\n",
    "            dx = 1\n",
    "        else:\n",
    "            dx = -1\n",
    "        \n",
    "        if startPos[1] <= homePos[1]:\n",
    "            dy = 1\n",
    "        else:\n",
    "            dy = -1\n",
    "        \n",
    "        return sum(rowCosts[i] for i in range(startPos[0] + dx, homePos[0] + dx, dx)) + sum(colCosts[i] for i in range(startPos[1] + dy, homePos[1] + dy, dy))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        ans=0\n",
    "        step= -1 if startPos[0]>homePos[0] else 1\n",
    "        for i in range(startPos[0]+step, homePos[0]+step, step):\n",
    "            ans+=rowCosts[i]\n",
    "        step= -1 if startPos[1]>homePos[1] else 1\n",
    "        for i in range(startPos[1]+step, homePos[1]+step, step):\n",
    "            ans+=colCosts[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        row_diff = homePos[0] - startPos[0]\n",
    "        col_diff = homePos[1] - startPos[1]\n",
    "        now_pos = startPos\n",
    "        cost = 0\n",
    "        while now_pos != homePos:\n",
    "            if row_diff > 0:\n",
    "                cost += rowCosts[now_pos[0] + 1]\n",
    "                now_pos[0] += 1\n",
    "                row_diff -= 1\n",
    "            elif row_diff < 0:\n",
    "                cost += rowCosts[now_pos[0] - 1]\n",
    "                now_pos[0] -= 1\n",
    "                row_diff += 1\n",
    "\n",
    "            if col_diff > 0:\n",
    "                cost += colCosts[now_pos[1] + 1]\n",
    "                now_pos[1] += 1\n",
    "                col_diff -= 1\n",
    "            elif col_diff < 0:\n",
    "                cost += colCosts[now_pos[1] - 1]\n",
    "                now_pos[1] -= 1\n",
    "                col_diff += 1\n",
    "        return cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, s: List[int], h: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        res = 0\n",
    "        if s[0] <= h[0]:\n",
    "            for i in range(min(s[0],h[0])+1,max(s[0],h[0])+1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(s[0]-1,h[0]-1,-1):\n",
    "                res += rowCosts[i]\n",
    "        if s[1] <= h[1]:\n",
    "            for i in range(min(s[1],h[1])+1,max(s[1],h[1])+1):\n",
    "                res += colCosts[i]\n",
    "        else:\n",
    "            for i in range(s[1]-1,h[1]-1,-1):\n",
    "                res += colCosts[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        if startPos[0]>homePos[0]:\n",
    "            dx=-1\n",
    "        else:\n",
    "            dx=1\n",
    "        if startPos[1]>homePos[1]:\n",
    "            dy=-1\n",
    "        else:\n",
    "            dy=1\n",
    "        ans=0\n",
    "        for i in range(startPos[0]+dx, homePos[0]+dx, dx):\n",
    "            ans+=rowCosts[i]\n",
    "        for i in range(startPos[1]+dy, homePos[1]+dy, dy):\n",
    "            ans+=colCosts[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        r1, c1 = startPos[0], startPos[1]\n",
    "        r2, c2 = homePos[0], homePos[1]\n",
    "        res = 0   # 总代价\n",
    "        # 移动至家所在行，判断行间移动方向并计算对应代价\n",
    "        if r2 >= r1:\n",
    "            for i in range(r1 + 1, r2 + 1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(r2, r1):\n",
    "                res += rowCosts[i]\n",
    "        # 移动至家所在位置，判断列间移动方向并计算对应代价\n",
    "        if c2 >= c1:\n",
    "            for i in range(c1 + 1, c2 + 1):\n",
    "                res += colCosts[i]\n",
    "        else:\n",
    "            for i in range(c2, c1):\n",
    "                res += colCosts[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, s: List[int], h: List[int], rs: List[int], cs: List[int]) -> int:\n",
    "        if s[0] == h[0] and s[1] == h[1]:\n",
    "            return 0\n",
    "        r, c = len(rs), len(cs)\n",
    "        \n",
    "        ans = 0\n",
    "        row_s, row_e = s[0], h[0]\n",
    "        if row_s >= row_e:\n",
    "            for i in range(row_s-1, row_e-1,-1):\n",
    "                ans += rs[i]\n",
    "        else:\n",
    "            for i in range(row_s+1, row_e+1):\n",
    "                ans += rs[i]\n",
    "\n",
    "        col_s, col_e = s[1], h[1]\n",
    "        if col_s >= col_e:\n",
    "            for i in range(col_s-1, col_e-1,-1):\n",
    "                ans += cs[i]\n",
    "        else:\n",
    "            for i in range(col_s+1, col_e+1):\n",
    "                ans += cs[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        ans1=0\n",
    "        ans2=0\n",
    "        if startPos==homePos:\n",
    "            return 0\n",
    "        while startPos[0]!=homePos[0]:\n",
    "            if startPos[0]>homePos[0]:\n",
    "                startPos[0]-=1\n",
    "                ans1+=rowCosts[startPos[0]]\n",
    "            if startPos[0]<homePos[0]:\n",
    "                startPos[0]+=1\n",
    "                ans1+=rowCosts[startPos[0]]\n",
    "        while startPos[1]!=homePos[1]:\n",
    "            if startPos[1]>homePos[1]:\n",
    "                startPos[1]-=1\n",
    "                ans2+=colCosts[startPos[1]]\n",
    "            if startPos[1]<homePos[1]:\n",
    "                startPos[1]+=1\n",
    "                ans2+=colCosts[startPos[1]]\n",
    "        return (ans1+ans2)\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "       \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "\n",
    "        x1, y1 = startPos\n",
    "        x2, y2 = homePos\n",
    "        res = 0\n",
    "        if x1 <= x2:\n",
    "            for i in range(x1+1, x2+1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(x2, x1):\n",
    "                res += rowCosts[i]\n",
    "        if y1 <= y2:\n",
    "            for j in range(y1+1, y2+1):\n",
    "                res += colCosts[j]\n",
    "        else:\n",
    "            for j in range(y2, y1):\n",
    "                res += colCosts[j]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        row_delta = col_delta = 1\n",
    "        if startPos[0] > homePos[0]:\n",
    "            row_delta = -1\n",
    "        if startPos[1] > homePos[1]:\n",
    "            col_delta = -1\n",
    "        \n",
    "        res = 0\n",
    "        for index in range(startPos[0] + row_delta, homePos[0] + row_delta, row_delta):\n",
    "            res += rowCosts[index]\n",
    "        for index in range(startPos[1] + col_delta, homePos[1] + col_delta, col_delta):\n",
    "            res += colCosts[index]\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        r1, c1 = startPos[0], startPos[1]\n",
    "        r2, c2 = homePos[0], homePos[1]\n",
    "        res = 0   # 总代价\n",
    "        # 移动至家所在行，判断行间移动方向并计算对应代价\n",
    "        if r2 >= r1:\n",
    "            for i in range(r1 + 1, r2 + 1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(r2, r1):\n",
    "                res += rowCosts[i]\n",
    "        # 移动至家所在位置，判断列间移动方向并计算对应代价\n",
    "        if c2 >= c1:\n",
    "            for i in range(c1 + 1, c2 + 1):\n",
    "                res += colCosts[i]\n",
    "        else:\n",
    "            for i in range(c2, c1):\n",
    "                res += colCosts[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def minCost(self, startPos, homePos, rowCosts, colCosts):\n",
    "        return (sum(rowCosts[startPos[0] + 1 : homePos[0] + 1]) if startPos[0] < homePos[0] else sum(rowCosts[homePos[0] : startPos[0]]) if startPos[0] > homePos[0] else 0) \\\n",
    "             + (sum(colCosts[startPos[1] + 1 : homePos[1] + 1]) if startPos[1] < homePos[1] else sum(colCosts[homePos[1] : startPos[1]]) if startPos[1] > homePos[1] else 0)        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "       \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        # dfs(i,j)从i，j到达终点的最小代价\n",
    "        # 因为cost都是正数，如果又绕过来l肯定代价会更大\n",
    "        sx,sy,tx,ty=startPos[0],startPos[1],homePos[0],homePos[1]\n",
    "        res=0\n",
    "        if sx<tx:\n",
    "            for row in range(sx+1,tx+1):\n",
    "                res+=rowCosts[row]\n",
    "        elif sx>tx:\n",
    "            for row in range(sx-1,tx-1,-1):\n",
    "                res+=rowCosts[row]\n",
    "        if sy<ty:\n",
    "            for row in range(sy+1,ty+1):\n",
    "                res+=colCosts[row]\n",
    "        elif sy>ty:\n",
    "            for row in range(sy-1,ty-1,-1):\n",
    "                res+=colCosts[row]\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        rs = 0\n",
    "        for i in range(min(startPos[0], homePos[0]), max(startPos[0], homePos[0])+1):\n",
    "            rs += rowCosts[i]\n",
    "        for j in range(min(startPos[1], homePos[1]), max(startPos[1], homePos[1])+1):\n",
    "            rs += colCosts[j]\n",
    "        return rs-colCosts[startPos[1]]-rowCosts[startPos[0]]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        r1, c1 = startPos[0], startPos[1]\n",
    "        r2, c2 = homePos[0], homePos[1]\n",
    "        res = 0  # 总代价\n",
    "        # 移动至家所在行，判断行间移动方向并计算对应代价\n",
    "        if r2 >= r1:\n",
    "            for i in range(r1 + 1, r2 + 1):\n",
    "                res += rowCosts[i]\n",
    "        else:\n",
    "            for i in range(r2, r1):\n",
    "                res += rowCosts[i]\n",
    "        # 移动至家所在位置，判断列间移动方向并计算对应代价\n",
    "        if c2 >= c1:\n",
    "            for i in range(c1 + 1, c2 + 1):\n",
    "                res += colCosts[i]\n",
    "        else:\n",
    "            for i in range(c2, c1):\n",
    "                res += colCosts[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, startPos: List[int], homePos: List[int], rowCosts: List[int], colCosts: List[int]) -> int:\n",
    "        y1, x1 = startPos\n",
    "        y2, x2 = homePos\n",
    "        if y1 <= y2:\n",
    "            dy = 1\n",
    "        else:\n",
    "            dy = -1\n",
    "        if x1 <= x2:\n",
    "            dx = 1\n",
    "        else:\n",
    "            dx = -1\n",
    "        ret = sum(rowCosts[y] for y in range(y1+dy, y2+dy, dy))\n",
    "        ret += sum(colCosts[x] for x in range(x1+dx, x2+dx, dx))\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumCost(self, start: list[int], target: list[int], specialRoads: list[list[int]]) -> int:\n",
    "        nodes = set([tuple(start), tuple(target)])\n",
    "        cost = collections.defaultdict(int)\n",
    "\n",
    "        for x1, y1, x2, y2, c in specialRoads:\n",
    "            if (x1, y1, x2, y2) not in cost:\n",
    "                cost[(x1, y1, x2, y2)] = c\n",
    "            else:\n",
    "                cost[(x1, y1, x2, y2)] = min(cost[(x1, y1, x2, y2)], c)\n",
    "            nodes.add((x1, y1))\n",
    "            nodes.add((x2, y2))\n",
    "\n",
    "        minHeap = [(0, start[0], start[1])]\n",
    "        visited = set()\n",
    "        minCost = {node: float('inf') for node in nodes}\n",
    "        minCost[(start[0], start[1])] = 0\n",
    "\n",
    "        while minHeap:\n",
    "            c, x, y = heapq.heappop(minHeap)\n",
    "            if (x, y) in visited:\n",
    "                continue\n",
    "            visited.add((x, y))\n",
    "\n",
    "            for nx, ny in nodes:\n",
    "                if (nx, ny) not in visited:\n",
    "                    sc = cost[(x, y, nx, ny)] if (x, y, nx, ny) in cost else float('inf')\n",
    "                    nc = min(sc, abs(nx-x)+abs(ny-y)) + c\n",
    "                    if nc < minCost[(nx, ny)]:\n",
    "                        minCost[(nx, ny)] = nc\n",
    "                        heapq.heappush(minHeap, (nc, nx, ny))\n",
    "\n",
    "        return minCost[(target[0], target[1])]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        ans = [-1]*n\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a,b,c in roads:\n",
    "            g[a-1].append((b-1, c))\n",
    "            g[b-1].append((a-1, c))\n",
    "        \n",
    "        def dijkstra(start):\n",
    "            dist = [float('inf')]*n\n",
    "            dist[start] = 0\n",
    "            mheap = [(0,start)]\n",
    "            while mheap:\n",
    "                dis,x = heapq.heappop(mheap)\n",
    "                if dis>dist[x]:\n",
    "                    continue\n",
    "                for nextN,nextD in g[x]:\n",
    "                    if dis+nextD < dist[nextN]:\n",
    "                        dist[nextN] = dis+nextD\n",
    "                        heapq.heappush(mheap, (dist[nextN], nextN))\n",
    "                pass\n",
    "            \n",
    "            cur_min = float('inf')\n",
    "            for i in range(n):\n",
    "                cur = (k+1)*dist[i] + appleCost[i]\n",
    "                cur_min = min(cur_min, cur) \n",
    "            return cur_min\n",
    "\n",
    "        for i in range(n):\n",
    "            ans[i] = dijkstra(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        e=collections.defaultdict(list)\n",
    "        for a,b,c in roads:\n",
    "            e[a].append((b,c*k+c))\n",
    "            e[b].append((a,c*k+c))\n",
    "        def dijk(start):\n",
    "            q=[(0,start)]\n",
    "            ret=appleCost[start-1]\n",
    "            find=[False]*(n+1)\n",
    "            while q:\n",
    "                cost,tp=heapq.heappop(q)\n",
    "                ret=min(ret,cost+appleCost[tp-1])\n",
    "                if find[tp]:\n",
    "                    continue\n",
    "                find[tp]=True\n",
    "                for i,newcost in e[tp]:\n",
    "                    if find[i]:\n",
    "                        continue\n",
    "                    heapq.heappush(q,(cost+newcost,i))\n",
    "            return  ret \n",
    "        ans=[0]*n\n",
    "        for i in range(n):\n",
    "            ans[i]=dijk(i+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        g = collections.defaultdict(list)\n",
    "        for a, b, c in roads:\n",
    "            g[a - 1].append((b - 1, c * (k + 1)))\n",
    "            g[b - 1].append((a - 1, c * (k + 1)))\n",
    "\n",
    "        visited = [0] * n\n",
    "        pq = sorted((c, i) for i, c in enumerate(appleCost))\n",
    "        while pq:\n",
    "            c, u = heapq.heappop(pq)\n",
    "            if visited[u]:\n",
    "                continue\n",
    "\n",
    "            visited[u] = 1\n",
    "            for v, nc in g[u]:\n",
    "                if appleCost[v] > c + nc:\n",
    "                    appleCost[v] = c + nc\n",
    "                    heapq.heappush(pq, (appleCost[v], v))\n",
    "\n",
    "        return appleCost\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappop, heappush\n",
    "from math import inf\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        adj = [[] for _ in range(n + 1)]\n",
    "        for u, v, cost in roads:\n",
    "            u -= 1\n",
    "            v -= 1\n",
    "            adj[u].append((v, (k + 1) * cost))\n",
    "            adj[v].append((u, (k + 1) * cost))\n",
    "        \n",
    "        # node n represents apple\n",
    "        for i, c in enumerate(appleCost):\n",
    "            adj[i].append((n, c))\n",
    "            adj[n].append((i, c))\n",
    "\n",
    "        # Dijkstra find shortest path from node n (apple) to every node\n",
    "        dist = [inf] * n + [0]\n",
    "        # heap stores (cost, node)\n",
    "        h = [(0, n)]\n",
    "        while h:\n",
    "            d, u = heappop(h)\n",
    "            if dist[u] < d:\n",
    "                continue\n",
    "            for v, w in adj[u]:\n",
    "                if dist[v] > d + w:\n",
    "                    dist[v] = d + w\n",
    "                    heappush(h, (d + w, v))\n",
    "            \n",
    "        return dist[:n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        g = collections.defaultdict(list)\n",
    "        for a, b, c in roads:\n",
    "            g[a - 1].append((b - 1, c * (k + 1)))\n",
    "            g[b - 1].append((a - 1, c * (k + 1)))\n",
    "\n",
    "        visited = [0] * n\n",
    "        pq = sorted((c, i) for i, c in enumerate(appleCost))\n",
    "        while pq:\n",
    "            c, u = heapq.heappop(pq)\n",
    "            if visited[u]:\n",
    "                continue\n",
    "\n",
    "            visited[u] = 1\n",
    "            for v, nc in g[u]:\n",
    "                if appleCost[v] > c + nc:\n",
    "                    appleCost[v] = c + nc\n",
    "                    heapq.heappush(pq, (appleCost[v], v))\n",
    "\n",
    "        return appleCost\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        cost = appleCost[::]\n",
    "        g = defaultdict(list)\n",
    "        for u, v, w in roads:\n",
    "            x, y, z = u - 1, v - 1, (k + 1) * w\n",
    "            g[x].append((y, z))\n",
    "            g[y].append((x, z))\n",
    "        h = []\n",
    "        for i, x in enumerate(appleCost):\n",
    "            heappush(h, (x,i))\n",
    "        while h:\n",
    "            cost, x = heappop(h)\n",
    "            if cost > appleCost[x]: continue\n",
    "            for y, w in g[x]:\n",
    "                if cost + w < appleCost[y]:\n",
    "                    appleCost[y] = cost + w \n",
    "                    heappush(h, (appleCost[y], y))\n",
    "        return appleCost\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for a, b, cost in roads:\n",
    "            g[a - 1].append([b - 1, cost])\n",
    "            g[b - 1].append([a - 1, cost])\n",
    "        \n",
    "        def dijkstra(start):\n",
    "            ans = inf\n",
    "            dist = [inf] * n\n",
    "            dist[start] = 0\n",
    "            q = [(0, start)]\n",
    "            while q:\n",
    "                cost, node = heapq.heappop(q)\n",
    "                ans = min(ans, cost * (k + 1) + appleCost[node])\n",
    "                if dist[node] < cost:\n",
    "                    continue\n",
    "                for nei, cost in g[node]:\n",
    "                    d = dist[node] + cost\n",
    "                    if d < dist[nei]:\n",
    "                        dist[nei] = d\n",
    "                        heapq.heappush(q, (d, nei))\n",
    "            return ans\n",
    "        return [dijkstra(i) for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for u, v, w in roads:\n",
    "            g[u - 1].append((v - 1, w))\n",
    "            g[v - 1].append((u - 1, w))\n",
    "        def dijkstra(i):\n",
    "            pq, visited, res = [(0, i)], set(), inf\n",
    "            while pq:\n",
    "                w, node = heappop(pq)\n",
    "                if node not in visited:\n",
    "                    visited.add(node)\n",
    "                    res = min(res, w + appleCost[node])\n",
    "                    for nei, weight in g[node]:\n",
    "                        heappush(pq, (w + weight * (k + 1), nei))\n",
    "            return res\n",
    "        return [dijkstra(i) for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for a, b, cost in roads:\n",
    "            g[a - 1].append([b - 1, cost])\n",
    "            g[b - 1].append([a - 1, cost])\n",
    "        \n",
    "        def dijkstra(start):\n",
    "            res, dist = inf, [inf] * n\n",
    "            dist[start], q = 0, [(0, start)]\n",
    "            while q:\n",
    "                cost, node = heapq.heappop(q)\n",
    "                res = min(res, cost * (k + 1) + appleCost[node])\n",
    "                for nei, cost in g[node]:\n",
    "                    d = dist[node] + cost\n",
    "                    if d < dist[nei]:\n",
    "                        dist[nei] = d\n",
    "                        heapq.heappush(q, (d, nei))\n",
    "            return res\n",
    "        return [dijkstra(i) for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        adj = [[] for _ in range(n + 1)]\n",
    "        for u, v, cost in roads:\n",
    "            u -= 1\n",
    "            v -= 1\n",
    "            adj[u].append((v, (k + 1) * cost))\n",
    "            adj[v].append((u, (k + 1) * cost))\n",
    "        \n",
    "        # node n represents apple\n",
    "        for i, c in enumerate(appleCost):\n",
    "            adj[i].append((n, c))\n",
    "            adj[n].append((i, c))\n",
    "\n",
    "        # Dijkstra find shortest path from node n (apple) to every node\n",
    "        dist = [inf] * n + [0]\n",
    "        # heap stores (cost, node)\n",
    "        h = [(0, n)]\n",
    "        while h:\n",
    "            d, u = heappop(h)\n",
    "            if dist[u] < d:\n",
    "                continue\n",
    "            for v, w in adj[u]:\n",
    "                if dist[v] > d + w:\n",
    "                    dist[v] = d + w\n",
    "                    heappush(h, (d + w, v))\n",
    "            \n",
    "        return dist[:n]\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for a, b, cost in roads:\n",
    "            g[a - 1].append([b - 1, cost])\n",
    "            g[b - 1].append([a - 1, cost])\n",
    "        \n",
    "        def dijkstra(start: int):\n",
    "            ans = float('inf')\n",
    "            dist = [float('inf')] * n\n",
    "            dist[start] = 0\n",
    "            q = [(0, start)]\n",
    "            while q:\n",
    "                cost, x = heapq.heappop(q)\n",
    "                ans = min(ans, cost * (k + 1) + appleCost[x])\n",
    "                if dist[x] < cost:\n",
    "                    continue\n",
    "                for y, cost in g[x]:\n",
    "                    d = dist[x] + cost\n",
    "                    if d < dist[y]:\n",
    "                        dist[y] = d\n",
    "                        heapq.heappush(q, (d, y))\n",
    "            return ans\n",
    "        \n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            ans[i] = dijkstra(i)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        graph = [set() for i in range(n + 1)]\n",
    "        for i, j, w in roads:\n",
    "            graph[i].add((j, w * (k + 1)))\n",
    "            graph[j].add((i, w * (k + 1)))\n",
    "        for j, w in enumerate(appleCost):\n",
    "            graph[0].add((j + 1, w))\n",
    "\n",
    "        answer = [100000] * (n + 1)\n",
    "        apple = []\n",
    "        answer[0] = 0\n",
    "        queue = [(0, 0)]\n",
    "        while len(queue) != 0:\n",
    "            nextW, nextP = heapq.heappop(queue)\n",
    "            if nextW > answer[nextP]:\n",
    "                continue\n",
    "            for each, eachW in graph[nextP]:\n",
    "                tmp = nextW + eachW\n",
    "                if answer[each] > tmp:\n",
    "                    answer[each] = tmp\n",
    "                    heapq.heappush(queue, (tmp, each))\n",
    "\n",
    "        return answer[1:]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for u, v, w in roads:\n",
    "            g[u - 1].append((v - 1, w))\n",
    "            g[v - 1].append((u - 1, w))\n",
    "        def dijkstra(i):\n",
    "            pq, d, res = [(0, i)], defaultdict(int), inf\n",
    "            while pq:\n",
    "                w, node = heappop(pq)\n",
    "                if node not in d:\n",
    "                    d[node] = w + appleCost[node]\n",
    "                    res = min(res, d[node])\n",
    "                    for nei, weight in g[node]:\n",
    "                        heappush(pq, (w + weight * (k + 1), nei))\n",
    "            return res\n",
    "        return [dijkstra(i) for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\r\n",
    "        g = defaultdict(list)\r\n",
    "        for a, b, cost in roads:\r\n",
    "            g[a - 1].append([b - 1, cost])\r\n",
    "            g[b - 1].append([a - 1, cost])\r\n",
    "        \r\n",
    "        def dijkstra(start: int):\r\n",
    "            ans = float('inf')\r\n",
    "            dist = [float('inf')] * n\r\n",
    "            dist[start] = 0\r\n",
    "            q = [(0, start)]\r\n",
    "            while q:\r\n",
    "                cost, x = heapq.heappop(q)\r\n",
    "                ans = min(ans, cost * (k + 1) + appleCost[x])\r\n",
    "                if dist[x] < cost:\r\n",
    "                    continue\r\n",
    "                for y, cost in g[x]:\r\n",
    "                    d = dist[x] + cost\r\n",
    "                    if d < dist[y]:\r\n",
    "                        dist[y] = d\r\n",
    "                        heapq.heappush(q, (d, y))\r\n",
    "            return ans\r\n",
    "        \r\n",
    "        ans = [0] * n\r\n",
    "        for i in range(n):\r\n",
    "            ans[i] = dijkstra(i)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for u, v, w in roads:\n",
    "            g[u - 1].append((v - 1, w))\n",
    "            g[v - 1].append((u - 1, w))\n",
    "        def dijkstra(i):\n",
    "            pq, d = [(0, i)], defaultdict(int)\n",
    "            while pq:\n",
    "                w, node = heappop(pq)\n",
    "                if node not in d:\n",
    "                    d[node] = w + appleCost[node]\n",
    "                    for nei, weight in g[node]:\n",
    "                        heappush(pq, (w + weight * (k + 1), nei))\n",
    "            return min(d.values())\n",
    "        return [dijkstra(i) for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        def dijkstra(i):\n",
    "            pq, d, g = [(0, i)], defaultdict(int), defaultdict(list)\n",
    "            for u, v, w in roads:\n",
    "                g[u - 1].append((v - 1, w))\n",
    "                g[v - 1].append((u - 1, w))\n",
    "            while pq:\n",
    "                w, node = heappop(pq)\n",
    "                if node not in d:\n",
    "                    d[node] = w + appleCost[node]\n",
    "                    for nei, weight in g[node]:\n",
    "                        heappush(pq, (w + weight * (k + 1), nei))\n",
    "            return min(d.values())\n",
    "        return [dijkstra(i) for i in range(n)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\r\n",
    "        g = collections.defaultdict(list)\r\n",
    "        for a, b, c in roads:\r\n",
    "            g[a - 1].append((b - 1, c * (k + 1)))\r\n",
    "            g[b - 1].append((a - 1, c * (k + 1)))\r\n",
    "        visit = [0] * n\r\n",
    "        pq = sorted((c, i) for i, c in enumerate(appleCost))\r\n",
    "        while pq:\r\n",
    "            c, u = heapq.heappop(pq)\r\n",
    "            if visit[u]:\r\n",
    "                continue\r\n",
    "            visit[u] = 1\r\n",
    "            for v, nc in g[u]:\r\n",
    "                if appleCost[v] > c + nc:\r\n",
    "                    appleCost[v] = c + nc\r\n",
    "                    heapq.heappush(pq, (appleCost[v], v))\r\n",
    "        return appleCost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b, w in roads:\n",
    "            g[a - 1].append([b - 1, (k + 1) * w])\n",
    "            g[b - 1].append([a - 1, (k + 1) * w])\n",
    "        ans = [inf] * n \n",
    "\n",
    "        def dij(start):\n",
    "            dis = [inf] * n \n",
    "            h = [[start, 0]]\n",
    "            while h:\n",
    "                a, d = heappop(h)\n",
    "                if d >= dis[a]:\n",
    "                    continue\n",
    "                dis[a] = d \n",
    "                for nxt, delta in g[a]:\n",
    "                    if dis[nxt] > delta + dis[a]:\n",
    "                        heappush(h, [nxt, delta + dis[a]])\n",
    "            return dis \n",
    "        \n",
    "        for i in range(n):\n",
    "            dis = dij(i)\n",
    "            for j in range(n):\n",
    "                ans[j] = min(ans[j], dis[j] + appleCost[i])\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        g = defaultdict(list)\n",
    "        for a, b, cost in roads:\n",
    "            g[a - 1].append([b - 1, cost])\n",
    "            g[b - 1].append([a - 1, cost])\n",
    "        \n",
    "        def dijkstra(start):\n",
    "            ans = inf\n",
    "            dist = [inf] * n\n",
    "            dist[start] = 0\n",
    "            q = [(0, start)]\n",
    "            while q:\n",
    "                cost, node = heapq.heappop(q)\n",
    "                ans = min(ans, cost * (k + 1) + appleCost[node])\n",
    "                # if dist[node] < cost:\n",
    "                #     continue\n",
    "                for nei, cost in g[node]:\n",
    "                    d = dist[node] + cost\n",
    "                    if d < dist[nei]:\n",
    "                        dist[nei] = d\n",
    "                        heapq.heappush(q, (d, nei))\n",
    "            return ans\n",
    "        return [dijkstra(i) for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hq\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        \n",
    "        ad=collections.defaultdict(list)\n",
    "\n",
    "        for s,e,v in roads:\n",
    "            ad[s].append([v,e])\n",
    "            ad[e].append([v,s])\n",
    "        ans=[]\n",
    "        for s in range(1,n+1):\n",
    "            dis={i:float(\"inf\") for i in range(1,n+1)}\n",
    "            dis[s]=0\n",
    "            heap=[]\n",
    "            hq.heappush(heap,[0,s])\n",
    "            vis=[0]*(n+1)\n",
    "            while heap:\n",
    "                d,cur=hq.heappop(heap)\n",
    "                if vis[cur]==1:\n",
    "                    continue\n",
    "                vis[cur]=1\n",
    "                for nexd,nex in ad[cur]:\n",
    "                    if vis[nex]==0:\n",
    "                        if d+nexd<dis[nex]:\n",
    "                            dis[nex]=d+nexd\n",
    "                            hq.heappush(heap,[d+nexd,nex])\n",
    "            mx=float(\"inf\")\n",
    "            for x in dis:\n",
    "                tmp=dis[x]+k*dis[x]+appleCost[x-1]\n",
    "                if tmp<mx:\n",
    "                    mx=tmp\n",
    "            ans.append(mx)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self,n:int,roads:List[List[int]],appleCost:List[int],k:int):\n",
    "        INF=0x3f3f3f3f3f3f3f3f\n",
    "        adj=[[] for _ in range(0,n+1)]                    #邻接表\n",
    "        for i in range(0,len(roads)):      #遍历roads建立邻接表\n",
    "            a,b=roads[i][0],roads[i][1]     #<a,b>:w\n",
    "            w=(k+1)*roads[i][2]\n",
    "            adj[a].append([b,w])\n",
    "            adj[b].append([a,w])\n",
    "        for i in range(1,n+1):         #建超级源点的边\n",
    "            adj[0].append([i,appleCost[i-1]])\n",
    "            adj[i].append([0,appleCost[i-1]])\n",
    "        dist=[INF for _ in range(0,n+1)]\n",
    "        dist[0]=0\n",
    "        pqu=[]                          #定义小根堆pqu,元素为[length,vno]\n",
    "        heapq.heappush(pqu,[0,0])      #源点元素进队\n",
    "        while pqu:\n",
    "            e=heapq.heappop(pqu)        #出队元素e\n",
    "            u=e[1]                      #出队顶点u\n",
    "            for edj in adj[u]:\n",
    "                v,w=edj[0],edj[1]\n",
    "                if dist[v]>dist[u]+w:    #边松驰\n",
    "                    dist[v]=dist[u]+w\n",
    "                    heapq.heappush(pqu,[dist[v],v])      #顶点v元素进队\n",
    "        ans=[0]*n\n",
    "        for i in range(1,n+1):\n",
    "            ans[i-1]=dist[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self,n:int,roads:List[List[int]],appleCost:List[int],k:int):\n",
    "        INF=0x3f3f3f3f3f3f3f3f\n",
    "        adj=[[] for _ in range(0,n+1)]                    #邻接表\n",
    "        for i in range(0,len(roads)):      #遍历roads建立邻接表\n",
    "            a,b=roads[i][0],roads[i][1]     #<a,b>:w\n",
    "            w=(k+1)*roads[i][2]\n",
    "            adj[a].append([b,w])\n",
    "            adj[b].append([a,w])\n",
    "        for i in range(1,n+1):         #建超级源点的边\n",
    "            adj[0].append([i,appleCost[i-1]])\n",
    "            adj[i].append([0,appleCost[i-1]])\n",
    "        dist=[INF for _ in range(0,n+1)]\n",
    "        dist[0]=0\n",
    "        pqu=[]                          #定义小根堆pqu,元素为[length,vno]\n",
    "        heapq.heappush(pqu,[0,0])      #源点元素进队\n",
    "        while pqu:\n",
    "            e=heapq.heappop(pqu)        #出队元素e\n",
    "            u=e[1]                      #出队顶点u\n",
    "            for edj in adj[u]:\n",
    "                v,w=edj[0],edj[1]\n",
    "                if dist[v]>dist[u]+w:    #边松驰\n",
    "                    dist[v]=dist[u]+w\n",
    "                    heapq.heappush(pqu,[dist[v],v])      #顶点v元素进队\n",
    "        ans=[0]*n\n",
    "        for i in range(1,n+1):\n",
    "            ans[i-1]=dist[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "INF = int(1e18)\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        START = n  # 虚拟源点\n",
    "        adjList = [[] for _ in range(n + 1)]\n",
    "        for u, v, w in roads:\n",
    "            u, v = u - 1, v - 1\n",
    "            adjList[u].append((v, w * (k + 1)))\n",
    "            adjList[v].append((u, w * (k + 1)))\n",
    "        for i in range(n):\n",
    "            adjList[START].append((i, appleCost[i]))\n",
    "            adjList[i].append((START, appleCost[i]))\n",
    "        dist = dijkstra(n + 1, adjList, START)\n",
    "        return dist[:-1]\n",
    "\n",
    "\n",
    "def dijkstra(n: int, adjList: Sequence[Sequence[Tuple[int, int]]], start: int) -> List[int]:\n",
    "    dist = [INF] * n\n",
    "    dist[start] = 0\n",
    "    pq = [(0, start)]\n",
    "\n",
    "    while pq:\n",
    "        curDist, cur = heappop(pq)\n",
    "        if dist[cur] < curDist:\n",
    "            continue\n",
    "        for next, weight in adjList[cur]:\n",
    "            cand = dist[cur] + weight\n",
    "            if cand < dist[next]:\n",
    "                dist[next] = cand\n",
    "                heappush(pq, (dist[next], next))\n",
    "    return dist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self,n:int,roads:List[List[int]],appleCost:List[int],k:int):\n",
    "        INF=0x3f3f3f3f3f3f\n",
    "        adj=[[] for _ in range(0,n+1)]                    #邻接表\n",
    "        for i in range(0,len(roads)):      #遍历roads建立邻接表\n",
    "            a,b=roads[i][0],roads[i][1]     #<a,b>:w\n",
    "            w=(k+1)*roads[i][2]\n",
    "            adj[a].append([b,w])\n",
    "            adj[b].append([a,w])\n",
    "        for i in range(1,n+1):         #建超级源点的边\n",
    "            adj[0].append([i,appleCost[i-1]])\n",
    "            adj[i].append([0,appleCost[i-1]])\n",
    "        dist=[INF for _ in range(0,n+1)]\n",
    "        dist[0]=0\n",
    "        pqu=[]                          #定义小根堆pqu,元素为[length,vno]\n",
    "        heapq.heappush(pqu,[0,0])      #源点元素进队\n",
    "        while pqu:\n",
    "            e=heapq.heappop(pqu)        #出队元素e\n",
    "            u=e[1]                      #出队顶点u\n",
    "            for edj in adj[u]:\n",
    "                v,w=edj[0],edj[1]\n",
    "                if dist[v]>dist[u]+w:    #边松驰\n",
    "                    dist[v]=dist[u]+w\n",
    "                    heapq.heappush(pqu,[dist[v],v])      #顶点v元素进队\n",
    "        ans=[0]*n\n",
    "        for i in range(1,n+1):\n",
    "            ans[i-1]=dist[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "from collections import deque, defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param roads:\n",
    "        :param appleCost:\n",
    "        :param k:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        m1 ={}\n",
    "        for k1,v in enumerate(appleCost):\n",
    "            m1[k1+1] = v\n",
    "        m2 = defaultdict(list)\n",
    "        for i in roads:\n",
    "            m2[i[0]].append((i[1], i[2]))\n",
    "            m2[i[1]].append((i[0], i[2]))\n",
    "        minv = min(appleCost)\n",
    "        dq = deque()\n",
    "        for i in m1:\n",
    "\n",
    "            dq.append((i, m1[i]))\n",
    "        m3 = {}\n",
    "        while dq:\n",
    "            first, v1 = dq.popleft()\n",
    "            ref = min(v1, m1[first])\n",
    "            if first not in m3:\n",
    "                m3[first] = ref\n",
    "            else:\n",
    "                if m3[first] <= ref:\n",
    "                    continue\n",
    "                m3[first] = ref\n",
    "            for i in m2[first]:\n",
    "                vv = i\n",
    "                newp = vv[1] * (k+1)\n",
    "                dq.append((vv[0], ref + newp))\n",
    "        ret = []\n",
    "        for i in range(1, n+1):\n",
    "            ret.append(m3.get(i, m1.get(i)))\n",
    "        return ret\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
